﻿#define _CRT_SECURE_NO_WARNINGS 1










//单调栈，顾名思义，就是具有单调性的栈。它依旧是⼀个栈结构，只不过⾥⾯存储的数据是递增或者递减的。这种结构是很容易实现的（如下⾯的代码），但重点是维护⼀个单调栈的意义是什么？


// 单调栈解决的问题
//单调栈能帮助我们解决以下四个问题：
//• 寻找当前元素左侧，离它最近，并且⽐它⼤的元素在哪；
//• 寻找当前元素左侧，离它最近，并且⽐它⼩的元素在哪；
//• 寻找当前元素右侧，离它最近，并且⽐它⼤的元素在哪；
//• 寻找当前元素右侧，离它最近，并且⽐它⼩的元素在哪。







//输⼊：
//9
//1 4 10 6 3 3 15 21 8
//输出：
//0 0 0 3 4 4 0 0 8

//
//#include<iostream>
//#include<stack>
//
//using namespace std;
//
//const int N = 3e6 + 10;
//
//int a[N], n;
//int ret[N];
//
//void test()
//{
//	stack<int> st;//维护一个单调递减的栈
//
//	for (int i = 1;i <= n;i++)
//	{
//		//栈里面小于等于a[i]的元素全部出栈
//		while (st.size() && a[st.top()] <= a[i])
//			st.pop();
//		
//		//此时栈顶元素存在，栈顶元素就是所求结果
//		if (st.size())
//			ret[i] = st.top();
//		
//		st.push(i);//存着是下标
//	}
//
//	for (int i = 1;i <= n;i++)
//		cout << ret[i] << " ";
//	cout << endl;
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 1;i <= n;i++)
//		cin >> a[i];
//
//	test();
//
//	return 0;
//}





//💡 总结：
//• 找左侧，正遍历；找右侧，逆遍历；
//• ⽐它⼤，单调减；⽐它⼩，单调增